﻿//-----------------------------------------------------------------------------
// Author: JCBDigger    @MistyManor
// http://Games.DiscoverThat.co.uk
// http://www.mistymanor.co.uk/
//-----------------------------------------------------------------------------

#region MIT License
/*
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#endregion

#region Using Statements
using System;
using System.Collections;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
#endregion

namespace Editor
{
    /// <summary>
    /// Algorithms to help calculate the view looking along a line passing over a grid.
    /// </summary>
    public class LineGridHelpers
    {
        // Bresenham's line algorithm.
        // http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
        // The algorithm does not guarantee to get every grid square crossed.
        // The following are existing implimentations I found quickly:
        // http://ericw.ca/notes/bresenhams-line-algorithm-in-csharp.html
        // http://www.codeproject.com/Articles/30686/Bresenham-s-Line-Algorithm-Revisited
        // My versions are not necessarily any better but are to my liking...

        /// <summary>
        /// Bresenham's line algorithm.
        /// This shows which pixels of a grid need to be on to show a line across that
        /// grid.
        /// The results can be in ANY DIRECTION from point (x0, y0) to point (x1, y1) or
        /// from point (x1, y1) to point (x0, y0)!  It depends on which quadrant the 
        /// start and finish points are in.
        /// 
        /// This was intended for use by plotters so it does not attempt to find every
        /// grid that a line passes over but finds a set of points that looks like a 
        /// straight line when viewed.
        /// 
        /// It is not a good choice for intersect calculations because it will skip
        /// potential impacts however it is fast so has other uses.
        /// 
        /// This is best used with a foreach loop because each iteration is only calculated 
        /// as needed.
        /// </summary>
        public static IEnumerable<Point> GetPointsOnLineAnyDirection(int x0, int y0, int x1, int y1)
        {
            bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
            if (steep)
            {
                int s;
                // Swap x0 and y0
                s = x0;
                x0 = y0;
                y0 = s;
                // Swap x1 and y1
                s = x1;
                x1 = y1;
                y1 = s;
            }
            if (x0 > x1)
            {
                int s;
                // Swap x0 and x1
                s = x0;
                x0 = x1;
                x1 = s;
                // Swap y0 and y1
                s = y0;
                y0 = y1;
                y1 = s;
            }
            int deltax = x1 - x0;
            int deltay = Math.Abs(y1 - y0);
            int error = deltax / 2;
            int ystep = (y0 < y1) ? 1 : -1;
            int y = y0;
            for (int x = x0; x <= x1; x++)
            {
                if (steep)
                {
                    yield return new Point(y, x);
                }
                else
                {
                    yield return new Point(x, y);
                }
                error = error - deltay;
                if (error < 0)
                {
                    y += ystep;
                    error += deltax;
                }
            }
            yield break;
        }
        /// <summary>
        /// Bresenham's line algorithm variation.
        /// This shows which pixels of a grid need to be on to show a line across that
        /// grid.
        /// The results are always from start point (x0, y0) to finish point (x1, y1)!
        /// 
        /// The original algorithm was intended for use by plotters so it does not attempt 
        /// to find every grid that a line passes over but finds a set of points that 
        /// looks like a straight line when viewed.
        /// This variation always plots from start to finish.
        /// 
        /// It is not a good choice for intersect calculations because it will skip
        /// potential impacts however it is fast so can be used where missing a few
        /// does not matter.  This variation being in order could be used for such 
        /// things as view occlusion calculations.
        /// 
        /// This is best used with a foreach loop because each iteration is only calculated 
        /// as needed.
        /// </summary>
        public static IEnumerable<Point> GetPointsOnLineStartToFinish(int x0, int y0, int x1, int y1)
        {
            int deltax = Math.Abs(x1 - x0);
            int deltay = Math.Abs(y1 - y0);
            int xstep = (x0 < x1) ? 1 : -1;
            int ystep = (y0 < y1) ? 1 : -1;
            int error1 = deltax - deltay;

            bool loop = true;
            while (loop)
            {
                yield return new Point(x0, y0);
                if (x0 == x1 && y0 == y1)
                {
                    loop = false;
                }
                else
                {
                    int error2 = 2 * error1;
                    if (error2 > -deltay)
                    {
                        error1 = error1 - deltay;
                        x0 = x0 + xstep;
                    }
                    if (error2 < deltax)
                    {
                        error1 = error1 + deltax;
                        y0 = y0 + ystep;
                    }
                }
            }
            yield break;
        }

#if DEBUG
        /////////////////////////////////////////////////////////////////////
        //
        #region Code Validation
        //
        /// <summary>
        /// Test to confirm what order the points are produced in.
        /// Outputs the list of points covered by a line in several directions
        /// covering at least all four quadrants from and to including zero.
        /// </summary>
        public static void ValidateGetPointsOnLineAnyDirection()
        {
            System.Diagnostics.Debug.WriteLine("\n== Start Test ===============================================");
            System.Diagnostics.Debug.WriteLine("== LineGridHelpers.GetPointsOnLineAnyDirection() ============");
            // List of points to test from
            Point[] pointTestsFrom = new Point[] 
            { 
                new Point(1, 1), // Right Upper
                new Point(1, -2), // Right Lower
                new Point(-2, -1), // Left Lower
                new Point(-1, -2), // Left Upper
                new Point(0, 0)  // Zero
            };
            // List of destinations to test
            Point[] pointTestsTo = new Point[] 
            { 
                new Point(10, 9), // Right Upper
                new Point(9, 2),
                new Point(9, -8), // Right Lower
                new Point(10, -2),
                new Point(-11, -8), // Left Lower
                new Point(-11, -1),
                new Point(-10, 9),  // Left Upper
                new Point(-10, 1)
            };

            foreach (Point pointFrom in pointTestsFrom)
            {
                foreach (Point pointTo in pointTestsTo)
                {
                    string output = "";
                    System.Diagnostics.Debug.WriteLine("\n" + 
                        "FROM point (" + pointFrom.X + ", " + pointFrom.Y + 
                        ") To point (" + pointTo.X + ", " + pointTo.Y + ") Output...");
                    foreach (Point pointOut in LineGridHelpers.GetPointsOnLineAnyDirection(pointFrom.X, pointFrom.Y, pointTo.X, pointTo.Y))
                    {
                        output += "(" + pointOut.X + ", " + pointOut.Y + ")|";
                    }
                    System.Diagnostics.Debug.WriteLine(output);
                }
            }
            System.Diagnostics.Debug.WriteLine("== End ======================================================\n");
        }
        /// <summary>
        /// Test to confirm what order the points are produced in.
        /// Outputs the list of points covered by a line in several directions
        /// covering at least all four quadrants from and to including zero.
        /// </summary>
        public static void ValidateGetPointsOnLineStartToFinish(bool graphicalOutput)
        {
            System.Diagnostics.Debug.WriteLine("\n== Start Test ===============================================");
            System.Diagnostics.Debug.WriteLine("== LineGridHelpers.GetPointsOnLineStartToFinish() ===========");
            // List of points to test from
            Point[] pointTestsFrom = new Point[] 
            { 
                new Point(1, 1), // Right Upper
                new Point(1, -2), // Right Lower
                new Point(-2, -1), // Left Lower
                new Point(-1, -2), // Left Upper
                new Point(0, 0)  // Zero
            };
            // List of destinations to test
            Point[] pointTestsTo = new Point[] 
            { 
                new Point(10, 9), // Right Upper
                new Point(9, 2),
                new Point(9, -8), // Right Lower
                new Point(10, -2),
                new Point(-11, -8), // Left Lower
                new Point(-11, -1),
                new Point(-10, 9),  // Left Upper
                new Point(-10, 1)
            };
            // To graphically display the output
            int graphMinValueX = int.MaxValue;
            int graphMaxValueX = int.MinValue;
            foreach (Point item in pointTestsTo)
            {
                graphMinValueX = Math.Min(graphMinValueX, item.X);
                graphMaxValueX = Math.Max(graphMaxValueX, item.X);
            }

            foreach (Point pointFrom in pointTestsFrom)
            {
                foreach (Point pointTo in pointTestsTo)
                {
                    string output = "";
                    System.Diagnostics.Debug.WriteLine("\n" + 
                        "FROM point (" + pointFrom.X + ", " + pointFrom.Y +
                        ") To point (" + pointTo.X + ", " + pointTo.Y + ") Output...");
                    if (graphicalOutput)
                    {
                        LineBorder(graphMinValueX, graphMaxValueX);
                    }
                    foreach (Point pointOut in LineGridHelpers.GetPointsOnLineStartToFinish(pointFrom.X, pointFrom.Y, pointTo.X, pointTo.Y))
                    {
                        if (graphicalOutput)
                        {
                            LineGraphX(pointOut, graphMinValueX, graphMaxValueX);
                        }
                        output += "(" + pointOut.X + ", " + pointOut.Y + ")|";
                    }
                    if (graphicalOutput)
                    {
                        LineBorder(graphMinValueX, graphMaxValueX);
                    }
                    System.Diagnostics.Debug.WriteLine(output);
                }
            }
            System.Diagnostics.Debug.WriteLine("== End ======================================================\n");
        }
        /// <summary>
        /// Display a horizontal border for the graph.
        /// </summary>
        private static void LineBorder(int graphMinValue, int graphMaxValue)
        {
            string output = "+";
            int length = graphMaxValue - graphMinValue + 3;
            for (int i = 0; i < length; i++)
            {
                output += "=";
            }
            output += "+";
            System.Diagnostics.Debug.WriteLine(output);
        }
        /// <summary>
        /// Use text to represent to position of the X value of the point.
        /// </summary>
        private static void LineGraphX(Point coord, int graphMinValue, int graphMaxValue)
        {
            string output = "|";
            int length = graphMaxValue - graphMinValue + 3;
            for (int i = 0; i < length; i++)
            {
                if (i - 1 + graphMinValue == coord.X)
                {
                    output += "X";
                }
                else
                {
                    output += "-";
                }
            }
            output += "|";
            output += "(" + coord.X + ", " + coord.Y + ")|";
            System.Diagnostics.Debug.WriteLine(output);
        }
        //
        #endregion
        //
        /////////////////////////////////////////////////////////////////////
#endif

    }
}
